home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor2 / simplex3.doc < prev    next >
Text File  |  1995-03-31  |  11KB  |  246 lines
  1. (User.programs) 
  2. Item: 437 by akcs.rmarimon@hpcvbbs.cv.hp.com [Ricardo Jose Marimon] 
  3. Subj: Solving Linear Programming Problems with SIMPLEX3 
  4. Date: 14 Nov 1992 
  5.  
  6. This solves linear programs using a "pseudo revised" simplex method. 
  7. It works very fast.  Take a look at it!!! 
  8.  
  9. [Note: "Linear Programming Problems" is mathematical jargon for what is 
  10.  simply a system of linear inequalities with the goal of maximizing a 
  11.  particular variable. 
  12.  
  13.  Concrete example: Suppose that the Sierra Cement Company has several 
  14.  cement trucks, drivers, delivery routes, and types of cement.  It is 
  15.  known that the sum of the costs of the delivery routes plus the drivers' 
  16.  pay must fall below some particular maximum.  And the other variables are 
  17.  similarly tied to given maximum values.  These inequalities are called 
  18.  "constraints".  If Sierra Cement wants to maximize their profit, they 
  19.  could spend all day doing "what-if" tinkering on a spreadsheet on a 
  20.  computer, or they could solve it in a few seconds using the Simplex 
  21.  method, which kicks out the absolute maximum possible profit, and the 
  22.  exact values of all the variables required to produce that maximum. Nice, 
  23.  eh?  Every business should use it, but few have even heard about it. 
  24.  Complete details can be found in any textbook about "Finite 
  25.  Mathematics".  -jkh-] 
  26.  
  27. SIMPLEX3 can solve a problem with 8 variables and 5 constraints in less 
  28. than 15 seconds performing 5 iterations on the tableau. 
  29.  
  30. The problem this program is intended to solve is of the form, 
  31.  
  32.         min    c.x 
  33.         st     A.x =  b    (* b must be greater than zero *) 
  34.                  x >= 0 
  35.  
  36. The way the problem is entered is as a matrix of the following form, 
  37.  
  38.              [ c | 0 | 0 ] 
  39.              [---+---+---] 
  40.              [ A | I | b ] 
  41.  
  42. Where I is the matrix formed by adding the slack and excess variables. 
  43. I is NOT necessarily the identity matrix. 
  44.  
  45. For example to solve the following problem 
  46.  
  47.            max x1 + 2 x2 + x3 
  48.            st 
  49.                x1 + x2      <= 3 
  50.                x1 - x2 + x3 <= 3 
  51.                     x2 + x3 <= 3 
  52.                x1 + x2 + x3 >= 3 
  53.                     x2      <= 2 
  54.                x1, x2, x3 >=0 
  55.  
  56. We convert it to the standard form 
  57.  
  58.            min - x1 - 2 x2 - x3 
  59.            st 
  60.                x1 + x2      + x4                     = 3 
  61.                x1 - x2 + x3      + x5                = 3 
  62.                     x2 + x3           + x6           = 3 
  63.                x1 + x2 + x3                - x7      = 3 
  64.                     x2                          + x8 = 2 
  65.                x1, x2, x3 >= 0 
  66.  
  67. And write it as a matrix to enter it in the program. 
  68.  
  69.           [[ -1 -2 -1 0 0 0  0 0 0 ] 
  70.            [  1  1  0 1 0 0  0 0 3 ] 
  71.            [  1 -1  1 0 1 0  0 0 3 ] 
  72.            [  0  1  1 0 0 1  0 0 3 ] 
  73.            [  1  1  1 0 0 0 -1 0 3 ] 
  74.            [  0  1  0 0 0 0  0 1 2 ]] 
  75.  
  76. This example matrix is included in the SIMPLEX3 directory under the 
  77. name "P". 
  78.  
  79. To solve this problem right away, enter the matrix [just press {alpha} 
  80. P {enter}  -jkh-], press the [INIT] key which initializes some of the 
  81. variables used by the program and then press the [SOLVE] key which 
  82. iterates and gives the solution in three parts as follows, 
  83.  
  84.            3:  :X: [ 2 .999999999998 2 0 0 0 2 1 ] 
  85.            2:  :\Gl: [ -1 0 -1 0 0 ] 
  86.            1:  :Z: -6 
  87.  
  88. Where x is the actual point that minimizes the problem, the \Gl (lambda) 
  89. is the solution to the dual problem or shadow prices of each of the 
  90. constraints, and Z is the objective function value at the point found to 
  91. be the minimum. 
  92.  
  93. This is the end of the quick start procedure to solve linear programming 
  94. problems with my program.  Now lets go to some details... 
  95.  
  96. The solutions of LP (linear programming problems) can be classified into: 
  97.  
  98.      unfeasible, when there is no point satisfying the set of constraints 
  99.      unbounded, when the set of constraints can not restrict the decrease 
  100.                 of the objective function (c.x) 
  101.      feasible & bounded, when there is a solution to the set of constraints 
  102.                          which minimizes the objective function value. 
  103.  
  104. The problem can handle all three cases, giving the solution when it is 
  105. feasible and bounded, providing a ray (which is a vector through which 
  106. you can infinitely decrease the objective function while remaining in 
  107. the feasible region) when the solution is unbounded, or flagging that 
  108. there is no feasible solution. 
  109.  
  110. To achieve the different solutions, the program goes through the two 
  111. phase simplex method automatically (you don't have to include artificial 
  112. variables).  Phase 1 is used to derive a starting basic feasible solution  
  113. by introducing a set of artificial variables whith the objective of 
  114. minimizing its sum; when this is achieved, the set of artificial 
  115. variables is removed and Phase 2 starts with the original objective 
  116. function.  (refer to any LP book for more details into the 2 phase 
  117. simplex method)  One important thing to notice, is that the columns 
  118. corresponding to the artificial variables, although not taken into 
  119. account on phase 2, are not removed from the problem because it is 
  120. sometimes usefull to have these columns at the end of the problem in 
  121. order to perform sensitivity analysis. 
  122.  
  123. The basic algorithm that I used to solve the problem is a pseudo 
  124. revised simplex method, where all that is maintained is the inverse of 
  125. the base, the set of basic and non basic variables, and the rest of 
  126. the data provided at the initialization process.  I think this is 
  127. the most effective procedure in terms of time because it requires less 
  128. computations... 
  129.  
  130. Here's a brief explanation of what the programs in the directory do. 
  131. This first set of programs are the ones intended to be used directly 
  132. to solve the problem: 
  133.  
  134.   [INIT]  Initializes the set of variables that are needed by the 
  135.           program. 
  136.   [TABL]  Provides the current tableau. 
  137.   [SOLU]  Extracts the solution from the current tableau. 
  138.   [SRAY]  Extracts a ray from an unbounded LP. 
  139.   [TRACE] Performs one iteration at a time; it is equivalent to solve, 
  140.           but you can take a look at the partial tableaus that are 
  141.           generated by the procedure.  [Great for homework or exams in 
  142.           Finite Mathematics courses, where you must show "your" work! 
  143.           -jkh-] 
  144.   [SOLVE] Gives the answer to the LP if it exists. 
  145.  
  146. This second set of programs should not be used directly unless you 
  147. REALLY know what you're doing.  There are some system-RPL programs 
  148. that can crash your system... 
  149.  
  150.   [ITER]  Given which variable enters and which variable exits, 
  151.           this program performs the necessary iterations.  Be careful 
  152.           because the numbers that this programs expects are the 
  153.           indices into the BVAR and NVAR variables corresponding to 
  154.           the basic and non-basic variables. 
  155.   [INVAR] Calculates which variable enters the base.  It returns 0 
  156.           if it is an optimum. 
  157.   [OUTVAR] Given which variable enters the base, it gives which 
  158.            variable must exit the base.  It returns 0 if the solution 
  159.            is unbounded. 
  160.   [PH1]   Performs all the calculations necessary to start phase 1. 
  161.   [PH2]   Same but for phase 2. 
  162.   [MCHOP] Given a matrix and the contents of the 'ZERO' variable 
  163.           if an element of the matrix is less than 'ZERO' in absolute 
  164.           value it changes it to 0. 
  165.   [MVIN]  Calculates the min element such that it is strictly less 
  166.           than zero.  It returns the index into the array corresponding 
  167.           to the element.  It returns 0 if no negative elements are 
  168.           found. 
  169.   [MVOUT] It performs the ratio test among two vectors. 
  170.           2: v2 
  171.           1: v1 
  172.           Returns i s.t. min over all i [ v1[i]/v2[i] for v2[i]>0 ] 
  173.           Returns 0 if all v2[i] are less or equal to 0. 
  174.   [MJOC]  Given two matrices it joins them in the standard form 
  175.           2: [ A ] 
  176.           1: [ B ]   It returns [ A | B ] 
  177.   [MSBC]  It takes the columns of a column as specified by a list 
  178.           with the numbers of the columns. 
  179.           2: [ A ] 
  180.           1: { 3 2 2 1}  It returns [ A3 A2 A2 A1 ] where Ai represents 
  181.           the ith column of A. 
  182.   [MELM]  This program is used to calculate the matrix that when 
  183.           multiplied by the inverse of the base, gives the new 
  184.           inverse. 
  185.           2: [1 2 4] 
  186.           1: 1        It returns [[ 1 0 0] 
  187.                                   [-2 1 0] 
  188.                                   [-4 0 1] 
  189.           Multyplying by this matrix is equivalent to performing 
  190.           row reduction in row 1 (as specified by element in level 1) 
  191.           given that the column involved is specified by the element 
  192.           in level 2. 
  193.   [MBASE] It quickly calculates wether there is a base in the system 
  194.           and if there is, which one it is.  It returns a list such that 
  195.           its elements correspond to the elements of the original matrix 
  196.           that corresponds to the the columns of the identity. 
  197.   [MSPL]  It just separates the original problem form, 
  198.  
  199.              [ c | 0 | 0 ] 
  200.              [---+---+---] 
  201.              [ A | I | b ] 
  202.  
  203.           Into the matrices [ A | I ], [ b ], and [ c ]. 
  204.   [CLR14] Clears the top 14 rows of the display. 
  205.  
  206. Here are the variables used by the above procedures.  Do not play with  
  207. these variables during a run of the problem because you might get  
  208. incorrect answers. 
  209.  
  210.   [ZERO]  Threshold after which numbers are considered to be zero. 
  211.           This in important because due to numeric problems, results 
  212.           tend to show some rounding errors. 
  213.   [BINV]  This is the inverse of the base. 
  214.   [ACST]  Actual cost function being used, it changes from phase 1 
  215.           to phase 2. 
  216.   [NVAR]  Non basic variables. 
  217.   [BVAR]  Basic variables, in the order in which they are in the  
  218.           inverse of the base. 
  219.   [COST]  The original objective function coefficients of the problem. 
  220.           The matrix [ c ] 
  221.   [DATA]  The matrix [ A | I ] 
  222.   [RSRC]  The matrix [ b ] 
  223.   [ARTI]  Number of artificial variables included. 
  224.   [COLS]  Number of variables in the problem, excluding artificials. 
  225.   [ROWS]  Number of constraints in the problem. 
  226.  
  227. The custom menu provides a quick access to all of these variables. 
  228.  
  229. I hope that most of the question will be answered by the above brief 
  230. description, but you can always contact me, and if I have time I will 
  231. get back yo you fairly soon. 
  232.  
  233.     Ricardo Marimon 
  234.     28-D Escondido Village 
  235.     Stanford CA 94305 
  236.  
  237.     Email: rmarimon@leland.stanford.edu 
  238.  
  239. Most of the bugs have already been worked out, but as Murphy says, there 
  240. is always one more bug...  Please send any bug reports to my email 
  241. address... 
  242.  
  243. Of course, I am not responsible for any damage that this program might 
  244. cause to your calculator, your job, yout studies, or your life...  :-) 
  245. But again, I haven't had any troubles for months. 
  246.